#include <stdio.h>
#include <stdlib.h>

/*
 * 链地址探查
 */

/*
  一：散列表创建方法
  A.直接定址
  B.数字分析
  C.平方取中
  D.折叠
  E.除留余数法

  二:解决冲突办法
  A.开放定址
     1.线性探查
     2.平方探查
     3.双散列函数探查
    
  B.链地址法

 */

struct node
{
  int data;
  struct node * next;
};

void insert(struct node * hash[], int data, int len)
{
  struct node * src;
  int i, d;

  //printf("insert node %p\n", hash);
  i = data % 13;
  src = (struct node *) malloc (sizeof(struct node));
  src->data = data;
  src->next = hash[i];
  hash[i] = src;
}

void creat_hash(struct node * hash[], int src[], int len)
{
  int i;

  for (i = 0; i < len; i++)
    insert(hash, src[i], len);  
}

int search(struct node * hash[],  int key, int * deep)
{
  struct node * src;
  int i, pos;

  pos = 1;
  i = key % 13;
  src = hash[i];
  *deep = 0;

  while ((src != NULL) && (src->data != key)) {
    src = src->next;
    pos++;
    *deep = pos;
  }

  if (src != NULL)
    return i;
  else
    return -1;
}

#define HASH_LEN 30
#define TABLE_LEN 9

void display(struct node * hash[])
{
  int i;

  for (i = 0; i < HASH_LEN; i++) {
    if (hash[i] == NULL)
      printf(" 0 ");
    else {
      printf(" %d ", hash[i]->data);
    }
  }
  printf("\n%d\n", hash[5]->next->data);
  printf("%d\n", hash[5]->next->next->data);
}

int main()
{
  struct node *node[30] ;
  int hash_data[] = {18, 75, 60, 43, 54, 90, 46, 70, 31};  // 70 18 被同样放在了5
  int key, i, pos, deep;

  for (i = 0; i < 30; i++) {
    node[i] = NULL;
  }

  //printf("%p \n", node);

  creat_hash(node, hash_data, TABLE_LEN);
  display(node);

  printf("input find key:");
  scanf("%d", & key);

  pos = -1;
  pos = search(node, key, &deep);
  if (pos != -1)
    printf("find successfuly, the key position %d deepth is %d.\n", pos, deep);
  else
    printf("find fial.\n");
}

